// https://leetcode.cn/problems/word-search-ii/?envType=study-plan-v2&envId=top-interview-150

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
private:
    int m, n;
    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};
private:
    struct TrieNode 
    {
        TrieNode* children[26] = {nullptr};
        string* word = nullptr;

        ~TrieNode()
        {
            for (int i = 0 ; i < 26 ; i++)
            {
                delete children[i];
            }
        }
    };
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) 
    {
        TrieNode* root = new TrieNode();
        for (string& word : words)
        {
            TrieNode* cur = root;
            for (const char& ch : word)
            {
                int index = ch - 'a';
                if (cur->children[index] == nullptr)
                {
                    cur->children[index] = new TrieNode();
                }
                cur = cur->children[index];
            }
            cur->word = &word;
        }

        m = board.size(), n = board[0].size();
        vector<string> ret;
        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                int index = board[i][j] - 'a';
                if (root->children[index] != nullptr)
                {
                    dfs(board, i, j, root, ret);
                }
            }
        }

        delete root;
        return ret;
    }
private:
    void dfs(vector<vector<char>>& board, int a, int b, TrieNode* cur, vector<string>& ret)
    {
        char ch = board[a][b];
        int index = ch - 'a';

        if (cur->children[index] == nullptr)
        {
            return ;
        }

        cur = cur->children[index];
        if (cur->word != nullptr)
        {
            ret.push_back(*cur->word);
            cur->word = nullptr;
        }

        board[a][b] = '#';
        for (int i = 0 ; i < 4 ; i++)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#')
            {
                dfs(board, x, y, cur, ret);
            }
        }
        board[a][b] = ch;
    }
};

int main()
{
    vector<vector<char>> board1 = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
    vector<string> words1 = {"oath","pea","eat","rain"};

    vector<vector<char>> board2 = {{'a','b'},{'c','d'}};
    vector<string> words2 = {"abcb"};

    Solution sol;

    auto vs1 = sol.findWords(board1, words1);
    auto vs2 = sol.findWords(board2, words2);

    for (const string& str : vs1)
    {
        cout << str << " ";
    }
    cout << endl;

    for (const string& str : vs2)
    {
        cout << str << " ";
    }
    cout << endl;

    return 0;
}